package com.leet.tree;

import java.util.Deque;
import java.util.LinkedList;

public class DiameterOfBinaryTree {
    public int diameterOfBinaryTree(TreeNode root) {
        if(root == null) return 0;
        Deque<TreeNode> dq = new LinkedList<>();
        dq.offer(root);
        int left = 0, right = 0;
        int ans = 0;
        while(!dq.isEmpty()){
            int size = dq.size();
            for(int i = 0 ; i < size; i++){
                TreeNode head = dq.poll();
                left = getHeight(head.left);
                right = getHeight(head.right);
                if(right+left > ans) ans = right+left;
                if(head.right != null) dq.offer(head.right);
                if(head.left != null) dq.offer(head.left);
            }
        }
        return ans;
    }
    private int getHeight(TreeNode root){
        if(root == null) return 0;
        Deque<TreeNode> q = new LinkedList<>();
        q.offer(root);
        int height = 0;
        // bfs
        while(!q.isEmpty()){
            int size = q.size();
            for(int i = 0;i < size; i++){
                TreeNode head = q.poll();
                if(head.left != null) q.offer(head.left);
                if(head.right != null) q.offer(head.right);
            }
            height++;
        }
        return height;
    }
}
